#include <iostream>
#include <string>
using namespace std;

struct node
{
	string name;
	float salary;
	node* next;  
};

void insert(node* &head, string newname, float newsalary)
{	
	node* newnode = new node;
	newnode->name = newname;
	newnode->salary = newsalary;

	newnode->next = head;
	head = newnode;	
}

void display(node* head)
{
	node* pRod = head;
	cout << "The link list is: \n";
	while(pRod != NULL)
	{
		cout << "Name: " << pRod->name << "  " << "Salary: " << pRod->salary << endl;
		pRod = pRod->next;
	}
	cout << endl;
}

void clear(node* &head)//delete link list function.????. 
{
	node*p;//define to be deleted node.
	while (head != NULL)
	{
		p = head;
		head = head->next;
		delete p;
	}
	cout << "the link list han been deleted!" << endl;
}
//
//Salary as a descending order,exchange the value of the two nodes to achieve sort.
//pRod is make node,p is current node.
//
void downsort(node* &head)
{
	if (head == NULL)
	{
		return;
	}
	else
	{
		node* new_head = new node;
		node* new_tail = new node;

		new_head->next = head;
		for (node* pTemp = head; pTemp != NULL; pTemp = pTemp->next)
		{
			if (pTemp->next == NULL) 
			{
				pTemp->next = new_tail;
				break;
			}
		}

		node* node_before_rod = new_head;
		for (node* pRod = head; pRod != new_tail; pRod = pRod->next)
		{
			node* node_before_current = pRod;
			for (node* p = pRod->next; p != new_tail; p = p->next)
			{
				if(p->salary > pRod->salary)
				{
					if (pRod == node_before_current) 
					{
						node_before_rod->next = p;
						pRod->next = p->next;
						p->next = pRod;
					}
					else
					{
						node_before_current->next = p->next;
						node_before_rod->next = p;
						p->next = pRod->next;
						pRod->next = node_before_current->next;
						node_before_current->next = pRod;
					}

					p = pRod;
					pRod = node_before_rod->next;
				}

				node_before_current = p;
			}
			
			node_before_rod = pRod;
		}

		node_before_rod->next = NULL;
		head = new_head->next;

		delete new_head;
		delete new_tail;
		return;
	}
}

int main()
{
	node* head = NULL;
	insert(head, "Jimmy", 1250.04);
	insert(head, "Tim", 1280.07);
	insert(head, "Rose", 1390.08);
	insert(head, "Tommy", 1490.35);
	insert(head, "Jon", 1320.54);
	display(head);

	cout << "Salary as a descending order : \n";
	downsort(head);
	display(head);

	clear(head);
	return 0;
}
